/**
 *  fileName:快速排序
 *  time:2024/4/24
 *  todo:$END$
 */
// let arr = [4, 2, 6, 9, 3, 8, 5, 1, 7]
// let arr = [3, 2, 1, 4]
// let arr = [2, 1]
let arr = [1, 2]
// let arr = [12, 36, 58, 4, 92, 37, 75, 38, 53, 51, 83, 41, 80, 67, 7, 85, 98, 89, 72, 65]
const swap = (arr, i1, i2) => {
  let temp = arr[i1]
  arr[i1] = arr[i2]
  arr[i2] = temp
}
const quicklySort = (arr, begin, end) => {
  if (begin >= end) return
  let left = begin + 1
  let right = end
  while (left < right) {
    while (left < right && arr[left] < arr[begin]) left++
    if(right === arr.length) right --
    while (left < right && arr[right] > arr[begin]) right--
    if (left < right) swap(arr, left, right)
  }
  let point = left === right ? left - 1 : right
  swap(arr, begin, point)
  quicklySort(arr, 0, point)
  quicklySort(arr, point + 1, end)
}
// const quicklySort = (arr, begin, end) => {
//   if (begin > end - 1) return
//   let left = begin
//   let right = end
//   do {
//     do left++; while (left < right && arr[left] < arr[begin])
//     do right--; while (left < right && arr[right] > arr[begin])
//     if (left < right) swap(arr, left, right)
//   } while (left < right)
//   let swapPoint = left === right ? right - 1 : right
//   swap(arr, begin, swapPoint)
//   quicklySort(arr, begin, swapPoint)
//   quicklySort(arr, swapPoint + 1, end)
// }
quicklySort(arr, 0, arr.length)
console.log(`arr ==> `, arr)
